A Universal Online Caching Algorithm Based on Pattern Matching.
We focus in this work on an aspect of online computation that is not addressed by the standard competitive analysis. Namely, identifying request sequences for which non-trivial online algorithms are useful versus request sequences for which all algorithms perform equally bad. The motivation for this work are advanced system and architecture designs which allow the operating system to dynamically allocate resources to online protocols such as prefetching and caching. To utilize these features the operating system needs to identify data streams that can benefit from more resources. Our approach in this work is based on the relation between entropy, compression and gambling, extensively studied in information theory. It has been shown that in some settings entropy can either fully or at least partially characterize the expected outcome of an iterative gambling game. Our goal is to study the extent to which the entropy of the input characterizes the expected performance of online algorithms for problems that arise in computer applications. We study bounds based on entropy for three classical online problems — list accessing, prefetching, and caching. Our bounds relate the performance of the best online algorithm to the entropy,
Noisy Constrained Capacity for BSC Channels.
Abstract — We study the classical problem of noisy constrained capacity in the case of the binary symmetric channel (BSC), namely, the capacity of a BSC whose input is a sequence from a constrained set. As stated in [4] “... while calculation of the noise-free capacity of constrained sequences is well known, the computation of the capacity of a constraint in the presence of noise... has been an unsolved problem in the half-century since Shannon’s landmark paper.... ” We first express the constrained capacity of a binary symmetric channel with (d, k)-constrained input as a limit of the top Lyapunov exponents of certain matrix random processes. Then, we compute asymptotic approximations of the noisy constrained capacity for cases where the noise parameter ε is small. In particular, we show that when k≤2d, the error term with respect to the constraint capacity is O(ε), whereas it is O(ε log ε) when k&gt; 2d. In both cases, we compute the coefficient of the error term. In the course of establishing these findings, we also extend our previous results on the entropy of a hidden Markov process to higher-order finite memory processes. These conclusions are proved by a combination of analytic and combinatorial methods. I.
Introduction to the special issue on information theory in molecular biology and neuroscience.

Tunstall code%2C Khodak variations%2C and random walks.
A variable-to-fixed length encoder partitions the source string into variable-length phrases that belong to a given and fixed dictionary. Tunstall, and independently Khodak, designed variable-to-fixed length codes for memoryless sources that are optimal under certain constraints. In this paper, we study the Tunstall and Khodak codes using analytic information theory, i.e., the machinery from the analysis of algorithms literature. After proposing an algebraic characterization of the Tunstall and Khodak codes, we present new results on the variance and a central limit theorem for dictionary phrase lengths. This analysis also provides a new argument for obtaining asymptotic results about the mean dictionary phrase length and average redundancy rates.
%28Un%29expected behavior of digital search tree profile.
A digital search tree (DST)  – one of the most fundamental data structure on words – is a digital tree in which keys (strings, words) are stored directly in (internal) nodes. Such trees find myriad of applications from the popular Lempel-Ziv’78 data compression scheme to distributed hash tables. The profile of a DST measures the number of nodes at the same distance from the root; it is a function of the number of stored strings and the distance from the root. Most parameters of DST (e.g., height, fill-up) can be expressed in terms of the profile. However, from the inception of DST, the analysis of the profile has been elusive and it has become a prominent open problem in the area of analysis of algorithms. We make here the first, but decisive step, towards solving this problem. We present a precise analysis of the average profile when stored strings are generated by a biased memoryless source. The main technical difficulty of analyzing the profile lies in solving a sophisticated recurrence equation. We present such a solution for the Poissonized version of the problem (i.e., when the number of stored strings is generated by a Poisson distribution) in the Mellin transform domain. To accomplish it, we introduce a novel functional operator that allows
Multiple choice tries and distributed hash tables.

Profiles of Tries.
Tries (from retrieval) are one of the most popular data structures on words. They are pertinent to (internal) structure of stored words and several splitting procedures used in diverse contexts. The profile of a trie is a parameter that represents the number of nodes (either internal or external) with the same distance from the root. It is a function of the number of strings stored in a trie and the distance from the root. Several, if not all, trie parameters such as height, size, depth, shortest path, and fill-up level can be uniformly analyzed through the (external and internal) profiles. Although profiles represent one of the most fundamental parameters of tries, they have been hardly studied in the past. The analysis of profiles is surprisingly arduous but once it is carried out it reveals unusually intriguing and interesting behavior. We present a detailed study of the distribution of the profiles in a trie built over random strings generated by a memoryless source. We first derive recurrences satisfied by the expected profiles and solve them asymptotically for all possible ranges of the distance from the root. It appears that profiles of tries exhibit several fascinating phenomena. When moving from the root to the leaves of a trie, the growth of the expected profiles vary. Near the root, the external profiles tend to zero in an exponentially rate, then the rate gradually rises to being logarithmic; the external profiles then abruptly tend to infinity, first logarithmically
Profile of Tries.
Tries (from retrieval) are one of the most popular data structures on words. They are pertinent to (internal) structure of stored words and several splitting procedures used in diverse contexts. The profile of a trie is a parameter that represents the number of nodes (either internal or external) with the same distance from the root. It is a function of the number of strings stored in a trie and the distance from the root. Several, if not all, trie parameters such as height, size, depth, shortest path, and fill-up level can be uniformly analyzed through the (external and internal) profiles. Although profiles represent one of the most fundamental parameters of tries, they have been hardly studied in the past. The analysis of profiles is surprisingly arduous but once it is carried out it reveals unusually intriguing and interesting behavior. We present a detailed study of the distribution of the profiles in a trie built over random strings generated by a memoryless source. We first derive recurrences satisfied by the expected profiles and solve them asymptotically for all possible ranges of the distance from the root. It appears that profiles of tries exhibit several fascinating phenomena. When moving from the root to the leaves of a trie, the growth of the expected profiles vary. Near the root, the external profiles tend to zero in an exponentially rate, then the rate gradually rises to being logarithmic; the external profiles then abruptly tend to infinity, first logarithmically
Annotating Pathways of Interaction Networks.
Integrating molecular interaction data with existing knowledge of molecular function reveals mechanisms that underly cellular organization. We present NARADA, a software tool that implements a comprehensive analysis suite for functional annotation of pathways. NARADA takes as input a species-specific molecular interaction network and annotation of biomolecules in the network and provides the user with a set of pathways composed of functional attributes, which may be thought of pathway templates in the functional annotation space that recur in various contexts (different groups of specific molecules with similar functional annotation patterns) in the molecular interaction network. NARADA has its underpinnings in formal statistical measures of significance, and algorithmic bases for performance. Comprehensive evaluation on the E. coli transcriptional regulation and proteinprotein interaction data demonstrate NARADA’s ability to detect known, as well as novel pathways. 1.
A One%2Dto%2DOne Code and Its Anti%2DRedundancy.
One-to-one codes are “one shot ” codes that assign a distinct codeword to source symbols and are not necessarily prefix codes (more generally, uniquely decodable). For example, such codes arise when there exists an “end of message ” channel symbol. Interestingly, as Wyner proved in 1972, for such codes the average code length can be smaller than the source entropy. By how much? We call this difference the anti-redundancy. Various authors over the years have shown that the anti-redundancy can be as big as minus the logarithm of the source entropy. However, to the best of our knowledge precise estimates do not exist. In this note, we consider a block code of length n generated by a binary memoryless source, and prove that the average anti-redundancy is − 1 2 log2 n + C + H(n)+o(1) where C is a constant and either H(n) =0iflog2(1 − p)/p is irrational (where p is the probability of generating a “0”) or otherwise H(n) is a fluctuating function as the code length increases. This relatively simple finding requires a combination of quite sophisticated analytic tools such as precise evaluation of Bernoulli sums, the saddle point method, and theory of distribution of sequences modulo 1.
On the Construction of %28Explicit%29 Khodak%27s Code and Its Analysis.

On the entropy of a hidden Markov process.
We study the entropy rate of a binary hidden Markov process (HMP) defined by observing the output of a binary symmetric channel whose input is a first-order binary Markov process. Despite the simplicity of the models involved, the characterization of this entropy is a long standing open problem. By presenting the probability of a sequence under the model as a product of random matrices, we show that the entropy rate sought is a top Lyapunov exponent of the product, which explains the di#culty in its explicit computation. We apply the same product of random matrices to derive an explicit expression for a first order Taylor approximation of the entropy rate with respect to the parameter of the binary symmetric channel. The accuracy of the approximation is validated against empirical simulation results. We also extend our results to Renyi&#039;s entropy of any order.

Functional annotation of regulatory pathways.
Motivation: Standardized annotations of biomolecules in interaction networks (e.g., Gene Ontology) provide comprehensive understanding of the function of individual molecules. Extending such annotations to pathways is a critical component of functional characterization of cellular signaling at the systems level. Results: We propose a framework for projecting gene regulatory networks onto the space of functional attributes using multigraph models, with the objective of deriving statistically significant pathway annotations. We first demonstrate that annotations of pairwise interactions do not generalize to indirect relationships between processes. Motivated by this result, we formalize the problem of identifying statistically over-represented pathways of functional attributes. We establish the hardness of this problem by demonstrating the non-monotonicity of common statistical significance measures. We propose a statistical model that emphasizes the modularity of a pathway, evaluating its significance based on the coupling of its building blocks. We complement the statistical model by an efficient algorithm and software, NARADA, for computing significant pathways in large regulatory networks. Comprehensive results from our methods applied to the E. coli transcription network demonstrate that our approach is effective in identifying known, as well as novel biological pathway annotations. Availability: NARADA is implemented in Java and is available at

Partial fillup and search time in LC tries.

Identifying statistical dependence in genomic sequences via mutual information estimates

Waiting Time Distributions for Pattern Occurrence in a Constrained Sequence.
A binary sequence of zeros and ones is called a (d, k)-sequence if it does not contain runs of zeros of length either less than d or greater than k, where d and k are arbitrary, but fixed, non-negative integers and d &lt; k. Such sequences find an abundance of applications in communications, in particular for magnetic and optical recording. Occasionally, one requires that (d, k)-sequences do not contain a specific pattern w. Therefore, distribution results concerning pattern occurrence in (d, k)-sequences are of interest. In this paper we study the distribution of the waiting time until the r-th occurrence of a pattern w in a random (d, k)-sequence generated by a Markov source. Numerical examples are also provided.
Randomized leader election.
We investigate the duration of an elimination process for identifying a winner by coin tossing, or, equivalently, the height of a random incomplete trie. Applications of the process include the election of a leader in a computer network. Using direct probabilistic arguments we obtain exact expressions for the discrete distribution and the moments of the height. Elementary approximation techniques then yield asymptotics for the distribution. We show that no limiting distribution exists, as the asymptotic expressions exhibit periodic fluctuations. In many similar problems associated with digital trees, no such exact expressions can be derived. We therefore outline a powerful general approach, based on the analytic techniques of Mellin transforms, Poissonization, and de-Poissonization, from which distributional asymptotics for the height can also be derived. In fact, it was this complex variables approach that led to our original discovery of the exact distribution. Complex analysis metho...
Error Resilient LZ%2777 Data Compression Algorithms%2C Analysis%2C and Experiments.
Abstract—We propose a joint source–channel coding algorithm capable of correcting some errors in the popular Lempel–Ziv’77 (LZ’77) scheme without introducing any measurable degradation in the compression performance. This can be achieved because the LZ’77 encoder does not completely eliminate the redundancy present in the input sequence. One source of redundancy can be observed when an LZ’77 phrase has multiple matches. In this case, LZ’77 can issue a pointer to any of those matches, and a particular choice carries some additional bits of information. We call a scheme with embedded redundant information the LZS’77 algorithm. We analyze the number of longest matches in such a scheme and prove that it follows the logarithmic series distribution with mean Ia � (plus some fluctuations), where � is the source entropy. Thus, the distribution associated with the number of redundant bits is well concentrated around its mean, a highly
Assessing Significance of Connectivity and Conservation in Protein Interaction Networks.
Computational and comparative analysis of protein-protein interaction (PPI) networks enable understanding of the modular organization of the cell through identification of functional modules and protein complexes. These analysis techniques generally rely on topological features such as connectedness, based on the premise that functionally related proteins are likely to interact densely and that these interactions follow similar evolutionary trajectories. Significant recent work in our lab, and in other labs has focused on efficient algorithms for identification of modules and their conservation. Application of these methods to a variety of networks has yielded novel biological insights. In spite of algorithmic advances, development of a comprehensive infrastructure for interaction databases is in relative infancy compared to corresponding sequence analysis tools such as BLAST and CLUSTAL. One critical component of this infrastructure is a measure of the statistical significance of a match or a dense subcomponent. Corresponding sequence-based measures such as E-values are key components of sequence matching tools. In the absence of an analytical measure, conventional methods rely on computer simulations based on ad-hoc models for quantifying significance. This paper presents the first such effort, to the best of our knowledge, aimed at analytically quantifying statistical significance
Error%2DResilient LZW Data Compression.

Assessing Significance of Connectivity and Conservation in Protein Interaction Networks.
Computational and comparative analysis of protein-protein interaction (PPI) networks enable understanding of the modular organization of the cell through identification of functional modules and protein complexes. These analysis techniques generally rely on topological features such as connectedness, based on the premise that functionally related proteins are likely to interact densely and that these interactions follow similar evolutionary trajectories. Significant recent work in our lab, and in other labs has focused on efficient algorithms for identification of modules and their conservation. Application of these methods to a variety of networks has yielded novel biological insights. In spite of algorithmic advances, development of a comprehensive infrastructure for interaction databases is in relative infancy compared to corresponding sequence analysis tools such as BLAST and CLUSTAL. One critical component of this infrastructure is a measure of the statistical significance of a match or a dense subcomponent. Corresponding sequence-based measures such as E-values are key components of sequence matching tools. In the absence of an analytical measure, conventional methods rely on computer simulations based on ad-hoc models for quantifying significance. This paper presents the first such effort, to the best of our knowledge, aimed at analytically quantifying statistical significance
Preface.
part of a series of studies in support of the California Governor’s Advisory Committee on Education Excellence. i PREFACE i LIST OF FIGURES iv
Multicast tree structure and the power law.
Abstract — In this paper we investigate structural properties of multicast trees that give rise to the so called multicast power law. The law asserts that the ratio R(n) of the average number of links in a multicast tree connecting the source to n destinations to the average number of links in a unicast path, satis es asymptotically R(n) cn; 0 &lt; &lt; 1: In order to obtain a better insight we rst analyze some simple multicast tree topologies, which under appropriately chosen parameters give rise to the multicast power law. The asymptotic analysis of R(n) in this case, indicates that it is very dif cult to infer the validity of power law by observing graphs of R(n) alone. Next we introduce a new metric, “reachability degre”, which is easy to measure and applicable to general networks where multicast trees are constructed as subtrees of a given spanning tree which we call Global Multicast Tree. The reachability degree is indicative of the structure of the Global Multicast Tree. We show that this metric provides a more reliable means for inferring the validity of the power law. Finally, we perform experiments on real and simulated networks to demonstrate the use of the new metric.
Hidden word statistics.
We consider the sequence comparison problem, also known as &#034;hidden&#034; pattern problem, where one searches for a given subsequence in a text (rather than a string understood as a sequence of consecutive symbols). A characteristic parameter is...
Pairwise Alignment of Protein Interaction Networks.
With an ever-increasing amount of available data on protein–protein interaction (PPI) networks and research revealing that these networks evolve at a modular level, discovery of conserved patterns in these networks becomes an important problem. Although available data on protein–protein interactions is currently limited, recently developed algorithms have been shown to convey novel biological insights through employment of elegant mathematical models. The main challenge in aligning PPI networks is to define a graph theoretical measure of similarity between graph structures that captures underlying biological phenomena accurately. In this respect, modeling of conservation and divergence of interactions, as well as the interpretation of resulting alignments, are important design parameters. In this paper, we develop a framework for comprehensive alignment of PPI networks, which is inspired by duplication/divergence models that focus on understanding the evolution of protein interactions. We propose a mathematical model that extends the concepts of match, mismatch, and gap in sequence alignment to that of match, mismatch, and duplication in network alignment and evaluates similarity between graph structures through a scoring function that accounts for evolutionary events. By relying on evolutionary models, the proposed framework facilitates interpretation of resulting alignments in terms of not only conservation but also divergence of modularity in PPI networks. Furthermore, as in the case of sequence alignment, our model allows flexibility in adjusting parameters to quantify underlying evolutionary relationships. Based on the proposed model, we formulate PPI network alignment as an optimization problem and present fast algorithms to solve this problem. Detailed experimental results from an implementation of the proposed framework show that our algorithm is able to discover conserved interaction patterns very effectively, in terms of both accuracies and computational cost. Key words: protein–protein interactions, network alignment, evolutionary models. 1.
Detecting Conserved Interaction Patterns in Biological Networks.
Molecular interaction data plays an important role in understanding biological processes at a modular level by providing a framework for understanding cellular organization, functional hierarchy, and evolutionary conservation. As the quality and quantity of network and interaction data increases rapidly, the problem of effectively analyzing this data becomes significant. Graph theoretic formalisms, commonly used for these analysis tasks, often lead to computationally hard problems due to their relation to subgraph isomorphism. This paper presents an innovative new algorithm, MULE, for detecting frequently occurring patterns and modules in biological networks. Using an innovative graph simplification technique based on ortholog contraction, which is ideally suited to biological networks, our algorithm renders these problems computationally tractable and scalable to large numbers of networks. We show, experimentally, that our algorithm can extract frequently occurring patterns in metabolic pathways and protein interaction networks from the KEGG, DIP, and BIND databases within seconds. When compared to existing approaches, our graph simplification technique can be viewed either as a pruning heuristic, or a closely related, but computationally simpler task. When used as a pruning heuristic, we show that our technique reduces effective graph sizes significantly, accelerating existing techniques by several orders of magnitude! Indeed, for most of the test cases, existing techniques could not even be applied without our pruning step. When used as a stand-alone analysis technique, MULE is shown to convey significant biological insights at near-interactive rates. The software, sample input graphs, and detailed results for comprehensive analysis of nine eukaryotic PPI networks are available at www.cs.purdue.edu/homes/koyuturk/mule. Key words: graph mining, frequent subgraph discovery, evolution, modular conservation. 1.
Finding biclusters by random projections.
Abstract. Given a matrix X composed of symbols, a bicluster is a submatrix of X obtained by removing some of the rows and some of the columns of X in such a way that each row of what is left reads the same string. In this paper, we are concerned with the problem of finding the bicluster with the largest area in a large matrix X. The problem is first proved to be NP-complete. We present a fast and efficient randomized algorithm that discovers the largest bicluster by random projections. A detailed probabilistic analysis of the algorithm and an asymptotic study of the statistical significance of the solutions are given. We report results of extensive simulations on synthetic data. 1
Finding biclusters by random projections.
Abstract. Given a matrix X composed of symbols, a bicluster is a submatrix of X obtained by removing some of the rows and some of the columns of X in such a way that each row of what is left reads the same string. In this paper, we are concerned with the problem of finding the bicluster with the largest area in a large matrix X. The problem is first proved to be NP-complete. We present a fast and efficient randomized algorithm that discovers the largest bicluster by random projections. A detailed probabilistic analysis of the algorithm and an asymptotic study of the statistical significance of the solutions are given. We report results of extensive simulations on synthetic data. 1
Enumeration of Binary Trees%2C Lempel%2DZiv%2778 Parsings%2C and Universal Types.
Abstract Binary unlabeled ordered trees (further called binarytrees) were studied at least since Euler, who enumerated them. The number of such trees with n nodes isnow known as the Catalan number. Over the years various interesting questions about the statistics of suchtrees were investigated (e.g., height and path length distributions for a randomly selected tree). Binarytrees find an abundance of applications in computer science. However, recently Seroussi posed a new andinteresting problem motivated by information theory considerations: how many binary trees of a givenpath length (sum of depths) are there? This question arose in the study of universal types of sequences.Seroussi declares that two sequences of length p havethe same universal type if they generate the same set of phrases in the incremental parsing of the Lempel-Ziv&#039;78 scheme. (He then proves that sequences of the same type converge to the same empirical distribution.)It turns out that the number of distinct types of sequences of length p corresponds to the number ofbinary (unlabeled and ordered) trees, Tp, of given pathlength p (and also the number of different Lempel-Ziv&#039;78parsings of length p sequences). We first show thatthe number of binary trees with given path length pis asymptotically equal to Tp, 22p/(log2 p). Then weestablish various limiting distributions for the number of nodes (number of phrases in the Lempel-Ziv&#039;78 scheme)when a tree is selected randomly among all Tp trees.Throughout, we use methods of analytic algorithmics
Pairwise Local Alignment of Protein Interaction Networks Guided by Models of Evolution.
Abstract. With ever increasing amount of available data on proteinprotein interaction (PPI) networks and research revealing that these networks evolve at a modular level, discovery of conserved patterns in these networks becomes an important problem. Recent algorithms on aligning PPI networks target simplified structures such as conserved pathways to render these problems computationally tractable. However, since conserved structures that are parts of functional modules and protein complexes generally correspond to dense subnets of the network, algorithms that are able to extract conserved patterns in terms of general graphs are necessary. With this motivation, we focus here on discovering protein sets that induce subnets that are highly conserved in the interactome of a pair of species. For this purpose, we develop a framework that formally defines the pairwise local alignment problem for PPI networks, models the problem as a graph optimization problem, and presents fast algorithms for this problem. In order to capture the underlying biological processes correctly, we base our framework on duplication/divergence models that focus on understanding the evolution of PPI networks. Experimental results from an implementation of the proposed framework show that our algorithm is able to discover conserved interaction patterns very effectively (in terms of accuracies and computational cost). While we focus on pairwise local alignment of PPI networks in this paper, the proposed algorithm can be easily adapted to finding matches for a subnet query in a database of PPI networks. 1
Markov Models for Identification of Significant Episodes.

Towards a complete characterization of tries.

Partial fillup and search time in LC tries

Enumeration of Binary Trees and Universal Types.
Binary unlabeled ordered trees (further called binary trees) were studied at least since Euler, who enumerated them. The number of such trees with n nodes is now known as the Catalan number. Over the years various interesting questions about the statistics of such trees were investigated (e.g., height and path length distributions for a randomly selected tree). Binary trees find an abundance of applications in computer science. However, recently Seroussi posed a new and interesting problem motivated by information theory considerations: how many binary trees of a given path length (sum of depths) are there? This question arose in the study of universal types of sequences. Two sequences of length p have the same universal type if they generate the same set of phrases in the incremental parsing of the Lempel-Ziv’78 scheme since one proves that such sequences converge to the same empirical distribution. It turns out that the number of distinct types of sequences of length p corresponds to the number of binary (unlabeled and ordered) trees, Tp, of given path length p (and also the number of distinct Lempel-Ziv’78 parsings of length p sequences). We first show that the number of binary trees with given path length p is asymptotically equal to Tp ∼ 2 2p/(log 2 p)(1+O(log−2/3 p)). Then we establish various limiting distributions for the number of nodes (number of phrases in the Lempel-Ziv’78 scheme) when a tree is selected randomly among all trees of given path length p. Throughout, we use methods of analytic algorithmics such as generating functions and complex asymptotics, as well
An optimal DNA segmentation based on the MDL principle.
The biological world is highly stochastic and inhomogeneous in its behavior. There  are regions in DNA with high concentration of G or C bases; stretches of sequences with  an abundance of CG dinucleotide (CpG islands); coding regions with strong periodicityof  -three pattern, and so forth. The transition between homogeneous and inhomogeneous  regions of DNA, known also as change points, carry important biological information. Computational  methods used to identify these homogeneous regions are called segmentations.
Reliable detection of episodes in event sequences.
Suppose one wants to detect \bad&#034; or \suspicious&#034; subsequences in event sequences. Whether an  observed pattern of activity (in the form of a particular subsequence) is signi  cant and should be a  cause for alarm, depends on how likely it is to occur fortuitously. A long enough sequence of observed  events will almost certainly contain any subsequence, and setting thresholds for alarm is an important  issue in a monitoring system that seeks to avoid false alarms. Suppose a long sequence T of observed  events contains a suspicious subsequence pattern S within it, where the suspicious subsequence S  consists of m events and spans a window of size w within T . We address the fundamental problem: is a  certain number of occurrences of a particular subsequence unlikely to be generated by randomness itself  (i.e., indicative of suspicious activity)? If the probability of an occurrence generated by randomness is  high and an automated monitoring system ags it as suspicious anyway, then such a system will suer  from generating too many false alarms. This paper quanti  es the probability of such an S occurring  in T within a window of size w, the number of distinct windows containing S as a subsequence, the  expected number of such occurrences, its variance, and establishes its limiting distribution that allows  to set up an alarm threshold so that the probability of false alarms is very small. We report on  experiments con  rming the theory and showing that we can detect bad subsequences with low false  alarm rate.
Probabilistic behavior of asymmetric level compressed tries.

Analysis of Randomized Selection Algorithm Motivated by the LZ%2777 Scheme.

Finding Biclusters by Random Projections.
Abstract. Given a matrix X composed of symbols, a bicluster is a submatrix of X obtained by removing some of the rows and some of the columns of X in such a way that each row of what is left reads the same string. In this paper, we are concerned with the problem of finding the bicluster with the largest area in a large matrix X. The problem is first proved to be NP-complete. We present a fast and efficient randomized algorithm that discovers the largest bicluster by random projections. A detailed probabilistic analysis of the algorithm and an asymptotic study of the statistical significance of the solutions are given. We report results of extensive simulations on synthetic data. 1
On the Average Sequence Complexity.
In this paper we study the average behavior of the number of distinct substrings in a text of size n over an alphabet of cardinality k. This quantity is called the complexity index and it captures the &#034;richness of the language&#034; used in a sequence. For example, sequences with low complexity index contain a large number of repeated substrings and they eventually become periodic (e.g., tandem repeats in a DNA sequence). In order to identify unusually low- or high-complexity strings one needs to determine how far are the complexities of the strings under study from the average or maximum string complexity. While the maximum string complexity was studied quite extensively in the past, to the best of our knowledge there are no results concerning the average complexity. We first prove that for a sequence generated by a mixing model (which includes Markov sources) the average complexity is asymptotically equal to n&amp;sup2;/2 which coincides with the maximum string complexity. However, for a memoryless source we establish a more precise result, namely the average string complexity is n&amp;sup2;/2 - n log_k n + (1+(1-&amp;gamma;)/ln k + &amp;phi;_k (log_k n)+ o(1))n where &amp;gamma; &amp;asymp; 0.577 and &amp;phi;_k(x) is a periodic function with a small amplitude for small alphabet size.
Biclustering Gene%2DFeature Matrices for Statistically Significant Dense Patterns.
Biclustering is an important problem that arises in diverse applications, including analysis of gene expression and drug interaction data. The problem can be formalized in various ways through different interpretation of data and associated optimization functions. We focus on the problem of finding unusually dense patterns in binary (0-1) matrices. This formulation is appropriate for analyzing experimental datasets that come from not only binary quantization of gene expression data, but also more comprehensive datasets such as gene-feature matrices that include functions of coded proteins and motifs in the coding sequence. We formalize the notion of an “unusually ” dense submatrix to evaluate the interestingness of a pattern in terms of statistical significance based on the assumption of a uniform memoryless source. We then simplify it to assess statistical significance of discovered patterns. Using statistical significance as an objective function, we formulate the problem as one of finding significant dense submatrices of a large sparse matrix. Adopting a simple iterative heuristic along with randomized initialization techniques, we derive fast algorithms for discovering binary biclusters. We conduct experiments on a binary gene-feature matrix and a quantized breast tumor gene expression matrix. Our experimental results show that the proposed method quickly discovers all interesting patterns in these datasets. 1.
On the Entropy of a Hidden Markov Process.
We study the entropy rate of a binary hidden Markov process (HMP) defined by observing the output of a binary symmetric channel whose input is a first-order binary Markov process. Despite the simplicity of the models involved, the characterization of this entropy is a long standing open problem. By presenting the probability of a sequence under the model as a product of random matrices, we show that the entropy rate sought is a top Lyapunov exponent of the product, which explains the di#culty in its explicit computation. We apply the same product of random matrices to derive an explicit expression for a first order Taylor approximation of the entropy rate with respect to the parameter of the binary symmetric channel. The accuracy of the approximation is validated against empirical simulation results. We also extend our results to Renyi&#039;s entropy of any order.
On the Average Sequence Complexity.
In this paper we study the average behavior of the number of distinct substrings in a text of size n over an alphabet of cardinality k. This quantity is called the complexity index and it captures the &#034;richness of the language&#034; used in a sequence. For example, sequences with low complexity index contain a large number of repeated substrings and they eventually become periodic (e.g., tandem repeats in a DNA sequence). In order to identify unusually low- or high-complexity strings one needs to determine how far are the complexities of the strings under study from the average or maximum string complexity. While the maximum string complexity was studied quite extensively in the past, to the best of our knowledge there are no results concerning the average complexity. We first prove that for a sequence generated by a mixing model (which includes Markov sources) the average complexity is asymptotically equal to n&amp;sup2;/2 which coincides with the maximum string complexity. However, for a memoryless source we establish a more precise result, namely the average string complexity is n&amp;sup2;/2 - n log_k n + (1+(1-&amp;gamma;)/ln k + &amp;phi;_k (log_k n)+ o(1))n where &amp;gamma; &amp;asymp; 0.577 and &amp;phi;_k(x) is a periodic function with a small amplitude for small alphabet size.
Detection of Significant Sets of Episodes in Event Sequences.
We present a method for a reliable detection of “unusual” sets of episodes in the form of many pattern sequences, scanned simultaneously for an occurrence as a subsequence in a large event stream within a window of size w. We also investigate the important special case of all permutations of the same sequence, which models the situation where the order of events in an episode does not matter, e.g., when events correspond to purchased market basket items. In order to build a reliable monitoring system we compare obtained measurements to a reference model which in our case is a probabilistic model (Bernoulli or Markov). We first present a precise analysis that leads to a construction of a threshold. The difficulties of carrying out a probabilistic analysis for an arbitrary set of patterns, stems from the possible
An efficient algorithm for detecting frequent subgraphs in biological networks.
With rapidly increasing amount of network and interaction data in molecular biology, the problem of effectively analyzing this data is an important one. Graph theoretic formalisms, commonly used for these analysis tasks, often lead to computationally hard problems due to their relation to subgraph isomorphism. This paper presents an innovative new algorithm for detecting frequently occurring patterns and modules in biological networks. Using an innovative graph simplification technique, which is ideally suited to biological networks, our algorithm renders these problems computationally tractable. Indeed, we show experimentally that our algorithm can extract frequently occurring patterns in metabolic pathways extracted from the KEGG database within seconds. The proposed model and algorithm are applicable to a variety biological networks either directly or with minor modifications. Implementation of the proposed algorithms in the C programming language is available as open source at http://www.cs.purdue.edu/homes/koyuturk/pathway/.
Special Issue on Analysis of Algorithms.

Precise minimax redundancy and regret.
Recent years have seen a resurgence of interest in redundancy of lossless coding. The  redundancy (regret) of universal  xed{to{variable length coding for a class of sources  determines by how much the actual code length exceeds the optimal (ideal over the  class) code length. In a minimax scenario one  nds the best code for the worst source  either in the worst case (called also maximal minimax) or on average. We  rst study the  worst case minimax redundancy over a class of stationary ergodic sources and replace  Shtarkov&#039;s bound by an exact formula. Among others, we prove that a generalized Shannon  code minimizes the worst case redundancy, derive asymptotically its redundancy,  and establish some general properties. This allows us to obtain precise redundancy  rates for memoryless, Markov and renewal sources. For example, we derive the exact  constant of the redundancy rate for memoryless and Markov sources by showing that  an integer nature of coding contributes log(log m=(m 1))= log m+ o(1) where m is the  size of the alphabet. Then we deal with the average minimax redundancy and regret. Our approach
Markov types and minimax redundancy for Markov sources.
Redundancy of universal codes for a class of sources determines by how much the actual code length exceeds the optimal code length. In the minimax scenario one designs the best code for the worst source within the class. Such minimax redundancy comes in two flavors: either on average or for individual sequences. The latter is also known as the maximal or the worst case minimax redundancy. We study the maximal minimax redundancy of universal block codes for Markovian sources of any order. We prove that the maximal minimax redundancy for Markov sources of order r is asymptotically equal to       1) log 2 n + log 2 A    (ln ln m  1/(m-1)  )/ ln m + o(1), where n is the length of a source sequence, m is the size of the alphabet and A  m is an explicit constant (e.g., we find that for a binary alphabet m = 2 and Markov of order r = 1 the constant        14.655449504 where G is the Catalan number). Unlike previous attempts, we view the redundancy problem as an asymptotic evaluation of certain sums over a set of matrices representing Markov types. The enumeration of Markov types is accomplished by reducing it to counting Eulerian paths in a multigraph. In particular, we propose an asymptotic formula for the number of strings of a given Markov type. All of these findings are obtained by analytic and combinatorial tools of analysis of algorithms. Index terms: Minimax redundancy, Markov sources, Markov types, Eulerian paths, multidimensional generating functions, analytic information theory. # A preliminary version of this paper was presented at Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, Versailles, 2002.
Problems on Sequences Information Theory and Computer Science Interface.

Markov types and minimax redundancy for Markov sources.
Redundancy of universal codes for a class of sources determines by how much the actual code length exceeds the optimal code length. In the minimax scenario one designs the best code for the worst source within the class. Such minimax redundancy comes in two flavors: either on average or for individual sequences. The latter is also known as the maximal or the worst case minimax redundancy. We study the maximal minimax redundancy of universal block codes for Markovian sources of any order. We prove that the maximal minimax redundancy for Markov sources of order r is asymptotically equal to       1) log 2 n + log 2 A    (ln ln m  1/(m-1)  )/ ln m + o(1), where n is the length of a source sequence, m is the size of the alphabet and A  m is an explicit constant (e.g., we find that for a binary alphabet m = 2 and Markov of order r = 1 the constant        14.655449504 where G is the Catalan number). Unlike previous attempts, we view the redundancy problem as an asymptotic evaluation of certain sums over a set of matrices representing Markov types. The enumeration of Markov types is accomplished by reducing it to counting Eulerian paths in a multigraph. In particular, we propose an asymptotic formula for the number of strings of a given Markov type. All of these findings are obtained by analytic and combinatorial tools of analysis of algorithms. Index terms: Minimax redundancy, Markov sources, Markov types, Eulerian paths, multidimensional generating functions, analytic information theory. # A preliminary version of this paper was presented at Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, Versailles, 2002.
On the number of full levels in tries.

On average sequence complexity.
In this paper we study the average behavior of the number of distinct substrings in a text of size n over an alphabet of cardinality k. This quantity is called the complexity index and it captures the &#034;richness of the language&#034; used in a sequence. For example, sequences with low complexity index contain a large number of repeated substrings and they eventually become periodic (e.g., tandem repeats in a DNA sequence). In order to identify unusually low- or high-complexity strings one needs to determine how far are the complexities of the strings under study from the average or maximum string complexity. While the maximum string complexity was studied quite extensively in the past, to the best of our knowledge there are no results concerning the average complexity. We first prove that for a sequence generated by a mixing model (which includes Markov sources) the average complexity is asymptotically equal to n&amp;sup2;/2 which coincides with the maximum string complexity. However, for a memoryless source we establish a more precise result, namely the average string complexity is n&amp;sup2;/2 - n log_k n + (1+(1-&amp;gamma;)/ln k + &amp;phi;_k (log_k n)+ o(1))n where &amp;gamma; &amp;asymp; 0.577 and &amp;phi;_k(x) is a periodic function with a small amplitude for small alphabet size.
An Optimal DNA Segmentation Based on the MDL Principle.
The biological world is highly stochastic and inhomogeneous in its behavior. There  are regions in DNA with high concentration of G or C bases; stretches of sequences with  an abundance of CG dinucleotide (CpG islands); coding regions with strong periodicityof  -three pattern, and so forth. The transition between homogeneous and inhomogeneous  regions of DNA, known also as change points, carry important biological information. Computational  methods used to identify these homogeneous regions are called segmentations.
Algorithms for Bounded%2DError Correlation of High Dimensional Data in Microarray Experiments.
The problem of clustering continuous valued data has been well studied in literature. Its application to microarray analysis relies on such algorithms as k-means, dimensionality reduction techniques, and graph-based approaches for building dendrograms of sample data. In contrast, similar problems for discrete-attributed data are relatively unexplored. An instance of analysis of discrete-attributed data arises in detecting co-regulated samples in microarrays. In this paper, we present an algorithm and a software framework, PROXIMUS, for error-bounded clustering of highdimensional discrete attributed datasets in the context of extracting co-regulated samples from microarray data. We show that PROXIMUS delivers outstanding performance in extracting accurate patterns of gene-expression.
Joint Source%2DChannel LZ%2777 Coding.

Reliable Detection of Episodes in Event Sequences.
Suppose one wants to detect \bad&#034; or \suspicious&#034; subsequences in event sequences. Whether an  observed pattern of activity (in the form of a particular subsequence) is signi  cant and should be a  cause for alarm, depends on how likely it is to occur fortuitously. A long enough sequence of observed  events will almost certainly contain any subsequence, and setting thresholds for alarm is an important  issue in a monitoring system that seeks to avoid false alarms. Suppose a long sequence T of observed  events contains a suspicious subsequence pattern S within it, where the suspicious subsequence S  consists of m events and spans a window of size w within T . We address the fundamental problem: is a  certain number of occurrences of a particular subsequence unlikely to be generated by randomness itself  (i.e., indicative of suspicious activity)? If the probability of an occurrence generated by randomness is  high and an automated monitoring system ags it as suspicious anyway, then such a system will suer  from generating too many false alarms. This paper quanti  es the probability of such an S occurring  in T within a window of size w, the number of distinct windows containing S as a subsequence, the  expected number of such occurrences, its variance, and establishes its limiting distribution that allows  to set up an alarm threshold so that the probability of false alarms is very small. We report on  experiments con  rming the theory and showing that we can detect bad subsequences with low false  alarm rate.

Analysis of Algorithms %28AofA%29 Part II 1998%2D2000 %28%22Princeton%2DBarcelona%2DGdansk%22%29.
This article is a continuation of our previous Algorithmic Column [54] (EATCS, 77,  2002) dedicated to activities of the Analysis of Algorithms group during the \Dagstuhl{  Period&#034; (1993-1997). The  rst three meetings took place in Schloss Dagstuhl, Germany.

Improved Behaviour of Tries by the %22Symmetrization%22 of the Source.
In this paper, we propose and study a pre-processing technique for improving performance of digital tree (trie)-based search algorithms under asymmetric memoryless sources. This technique (which we call a symmetrization of the source) bijectively maps the sequences of symbols from the original (asymmetric) source into symbols of an output alphabet resulting in a more uniform distribution. We introduce a criterion of efficiency for such a mapping, and demonstrate that a problem of finding an optimal for a given source (or universal) symmetrization transform is equivalent to a problem of constructing a minimum redundancy variable-length-to-block code for this source (or class of sources). Based on this result...
Semi%2Ddiscrete Matrix Transforms %28SDD%29 for Image and Video Compression.
| A wide variety of matrix transforms have been used for compression of image and video data. Transforms have also been used for motion estimation and quantization. One such transform is the singularvalue decomposition (SVD) that relies on low rank approximations of the matrix for computational and storage eciency. In this paper, we describe the use of a variant of SVD in image and video compression. This variant, rst proposed by Peleg and O&#039;Leary [5], called semi-discrete decomposition (SDD) restricts the elements of the outer product vectors to 0/1/-1. Thus approximations of much higher rank can be stored for the same amount of storage. We demonstrate the superiority of SDD over SVD for a variety of compression schemes. We also show that DCT-based compression is still superior to SDD-based compression. However, we demonstrate that SDD facilitates fast and accurate pattern matching and motion estimation; thus presenting excellent opportunities for improved compression.  I. Introducti...
Generalized Shannon Code Minimizes the Maximal Redundancy.
Source coding, also known as data compression, is an area of information theory that deals with the design and performance evaluation of optimal codes for data compression. In 1952 Huffman constructed his optimal code that minimizes the average code length among all prefix codes for known sources. Actually, Huffman codes minimizes the average redundancy defined as the difference between the code length and the entropy of the source. Interestingly enough, no optimal code is known for other popular optimization criterion such as the maximal redundancy defined as the maximum of the pointwise redundancy over all source sequences. We first prove that a generalized Shannon code minimizes the maximal redundancy among all prefix codes, and present an efficient implementation of the optimal code. Then we compute precisely its redundancy for memoryless sources. Finally, we study universal codes for unknown source distributions. We adopt the minimax approach and search for the best code for the worst source. We establish that such redundancy is a sum of the likelihood estimator and the redundancy of the generalize code computed for the maximum likelihood distribution. This replaces Shtarkov&#039;s bound by an exact formula. We also compute precisely the maximal minimax for a class of memoryless sources. The main findings of this paper are established by techniques that belong to the toolkit of the &#034;analytic analysis of algorithms&#034; such as theory of distribution of sequences modulo 1 and Fourier series. These methods have already found applications in other problems of information theory, and they constitute the so called analytic information theory.
Is the internet fractal%3F
One of the main bene#ts of multicast communication is the overall reduction of network load. To quantify this reduction, when compared to traditional unicast, experimental studies by Chuang and Sirbu indicated the so called power law which asserts that the number of links in a multicast delivery tree connecting a source to m #distinct# sites is in m    . In order to explain theoretically this behavior, Phillips, Shenker, and Tangmunarunkit examined approximately the link number for a V -ary complete tree topology, and concluded that this number grows nearly linearly with m, thus not obeying the power law. We #rst re-examine the analysis by Phillips et.al. and provide precise asymptotic expansion for the link number that con#rms the nearly linear #with some wobbling# growth. Claiming that the essence of the problem lies in the modeling assumptions, we replace the V -ary complete tree topology byaV -ary self-similar tree with similarity factor 0 # ##1. In such a tree a node at level k is replicated CV    times, where D is the depth of the tree and C is a constant. Under this assumption, we analyze again L#m# and prove that L#m# # cm    c is an explicitly computable constant. Hence self-similar trees provide a plausible explanation of the multicast power law. Next, we examine more general conditions for general trees, under which the power law still holds. We also discuss some experimental results in real networks that rea#rm the power law and show that in these networks the general conditions hold.
2D%2Dpattern matching image and video compression theory

Analytic variations on redundancy rates of renewal processes.
Csisz ar and Shields have recently proved that the minimax redundancy for a class of (stationary) renewal processes is ( n) where n is the block length. This interesting result provides a first non-trivial bound on redundancy for a non-parametric family of processes. The present paper gives a precise estimate of the redundancy rate for such (nonstationary) renewal sources, namely, 2 n +O(log n): This asymptotic expansion is derived by complex-analytic methods that include generating function representations, Mellin transforms, singularity analysis and saddle point estimates. This work places itself within the framework of analytic information theory.
A universal predictor based on pattern matching.

Optimal versus randomized search of fixed length binary words.
We consider the search problem in which one nds a binary word among m words chosen randomly from the set of all words of xed length n. It is well known that the optimal search is equivalent to the Human coding that requires on average log 2 m bits to be checked plus a small additional cost called the average redundancy. The latter is an oscillating function of m and is bounded between zero and 1 (1 + ln ln 2)= ln 2   0:0860713320. As a matter of fact, it is known that nding the optimal strategy for this problem is NP-hard. We propose here several simple randomized search strategies leading respectively to the following average redundancies: 1:332746177, 0:6113986565, 0:4310617764, and 0:332746177, plus some small oscillations that we characterize quite precisely. These results should be compared to the optimal, but NP-hard, search algorithm. Our ndings extend and make more precise recent results of Fedotov and Ryabko. They are obtained by analytic methods such as generating functions, Mellin transform, and analytic depoissonization.  
Limit laws for the height in PATRICIA tries.

The height of a binary search tree the limiting distribution perspective.
We study the height of the binary search tree-- the most fundamental data structure used for searching. We assume that the binary search tree is built from a random permutation of n elements. Under this assumption, we study the limiting distribution of the height as n! 1. We show that the distribution has six asymptotic regions (scales). These correspond to different ranges of k and n where PrfH n kg is the height distribution. In the critical region (the so--called central region), where most of the probability mass is concentrated, the limiting distribution satisfies a non-linear integral equation. While we cannot solve this equation exactly, we show that both tails of the distribution are roughly of a double exponential form. From our analysis we conclude that the average height E[H n]  A log n \Gamma
Real%2DTime Decompression of Streaming Video Using Mobile Code.

Average%2DCase Analysis of Algorithms %2D Preface.

Hidden Pattern Statistics.
 Two fundamental problems in combinatorics on words and string manipulation are string matching and sequence comparison. In string matching one searches for all occurrences of a given string,  understood as a sequence of consecutive symbols, in a text. In sequence comparison a subsequence rather than a string is searched in a text The string matching problem has been extensively studied in literature from algorithmic and probabilistic points of view. The sequence comparison problem, also known as  hidden pattern problem, is harder and it has been much less investigated. In this paper we study the number of occurrences of a given pattern w of length m as a subsequence in a random text of length  n generated by a memoryless source. In particular, we consider two versions of this problem, namely the unconstrained one in which the subsequence w can appear anywhere in the text, and the constrained  one that puts bounds on the distances between symbols of the word w. We determine the mean and the variance of the number of occurrences, and establish a Gaussian limit law. These results are obtained via combinatorics on words, formal languages, and methods of analytic combinatorics based on generating functions and moment methods. The motivation to study this problem comes from an attempt at finding a reliable threshold for intrusion detections, from textual data processing applications, and from molecular biology.   
Average%2DCase Analysis of Algorithms %2D Preface.

Average Profile of the Lempel%2DZiv Parsing Scheme for a Markovian Source.
For a Markovian source, we analyze the Lempel-Ziv parsing scheme that partitions sequences into phrases such that a new phrase is the shortest phrase not seen in the past. We consider three models: In the Markov Independent model, several sequences are generated  independently by Markovian sources, and the ith phrase is the shortest prefix of the ith  sequence that was not seen before as a phrase (i.e., a prefix of previous (i \Gamma 1) sequences). In the other two models, only a single sequence is generated by a Markovian source. In the second model, for which we coin the name Gilbert-Kadota model, a fixed number of phrases is generated according to the Lempel-Ziv algorithm, thus producing a sequence of a variable (random) length. In the last model, known also as the Lempel-Ziv model, a string of fixed length is partitioned into a variable (random) number of phrases. These three models can be efficiently represented and analyzed by digital search trees that are of interest to other al...
On the average redundancy rate of the Lempel%2DZiv code with the k%2Derror protocol.
In this paper we examine the average redundancy rate of a Lempel-Ziv&#039;78 code with the k-error protocol. Storer and Reif have studied this modification of the Lempel-Ziv scheme and showed that it provides an efficient protection against error propagation while preserving the asymptotic optimality of the code. We refine this result by providing an asymptotic expression for the average redundancy rate of this code for memoryless sources. Using analytic methods, we establish our result by exploiting a relationship between a parsing scheme of the Lempel-Ziv encoder with the k-error protocol and a generalization of the digital search tree structure. We accompany our analysis with a number of experiments that test the validity of our theoretical result and demonstrate the effects of various additional modifications of the Lempel-Ziv algorithm.
On the Average Redundancy Rate of the Lempel%2DZiv Code with K%2DError Protocol.
In this paper we examine the average redundancy rate of a Lempel-Ziv&#039;78 code with the k-error protocol. Storer and Reif have studied this modification of the Lempel-Ziv scheme and showed that it provides an efficient protection against error propagation while preserving the asymptotic optimality of the code. We refine this result by providing an asymptotic expression for the average redundancy rate of this code for memoryless sources. Using analytic methods, we establish our result by exploiting a relationship between a parsing scheme of the Lempel-Ziv encoder with the k-error protocol and a generalization of the digital search tree structure. We accompany our analysis with a number of experiments that test the validity of our theoretical result and demonstrate the effects of various additional modifications of the Lempel-Ziv algorithm.
Summary Structures for Frequency Queries on Large Transaction Sets.
As large-scale databases become commonplace, there has been significant  interest in mining them for commercial purposes. One of the basic tasks that  underlies many of these mining operations is querying of transaction sets for  frequencies of specified attribute values. The size of these databases makes it  important to develop summary structures capable of high compression ratios  as well as supporting fast frequency queries. The nature of the problem and  its differences with respect to traditional text compression allows very high  compression ratios.  In this paper, we propose a binary trie-based summary structure for representing  transaction sets. We demonstrate that this trie structure, when augmented  with an appropriate set of horizontal pointers, can support frequency  queries several orders of magnitude faster than raw transaction data. We improve  the memory characteristics of our scheme by compressing the trie into  a Patricia trie and demonstrate that this does not have...
Heights in Generalized Tries and PATRICIA Tries.

Height in a digital search tree and the longest phrase of the Lempel%2DZiv scheme.

Height in a digital search tree and the longest phrase of the Lempel%2DZiv scheme.

A Note on the Asymptotic Behavior of the Heights in b%2DTries for b Large.
We study the limiting distribution of the height in a generalized trie in which external nodes are capable to store up to b items (the so called b-tries). We assume that such a tree is built from n random strings (items) generated by an unbiased memoryless source. In this paper, we discuss the case when b and n are both large. We shall identify five regions of the height distribution that should be compared to three regions obtained for fixed b. We prove that for most n, the limiting distribution is concentrated at the single point k1 = ⌊log 2(n/b) ⌋ +1 as n, b → ∞. We observe that this is quite different than the height distribution for fixed b, in which case the limiting distribution is of an extreme value type concentrated around (1+1/b)log 2 n. We derive our results by analytic methods, namely generating functions and the saddle point method. We also present some numerical verification of our results. 1
Asymptotic average redundancy of Huffman %28and other%29 block codes.

Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel%2DZiv Scheme.

2D%2DPattern Matching Image and Video Compression.
In this paper, we present a lossy data compression scheme based on an approximate two  dimensional pattern matching (2D-PMIC) extension of the Lempel-Ziv lossless scheme. We  apply the scheme to image and video compression and report on our theoretical and experimental  results. Theoretically, we show that the so called fixed database model leads to suboptimal  compression. Furthermore, the compression ratio of this model is as low as the generalized  entropy that we define in the paper. We use this model for our video compression scheme  and present experimental results. For image compression we use a growing database model for  which we provide an approximate analysis (which will be presented in the final version of the  paper). The implementation of 2D-PMIC is a challenging problem from the algorithmic point  of view. We use a range of novel techniques and data structures such as k-d trees, generalized  run length coding, adaptive arithmetic coding, and variable and adaptive maximum distortion  level to achieve good compression ratios at high compression speeds. We demonstrate bit rates  in the range of 0:25 \Gamma 0:5 bpp for high quality images and data rates in the range of 0:15 \Gamma 0:4  Mbps for video compression.
Quicksort Algorithm Again Revisited.
this paper, we establish an integral equation for the probability density of the number of comparisons L n . Then, we investigate the large deviations of L n . We shall show that the left tail of the limiting distribution is much &#034;thinner&#034; (i.e., double exponential) than the right tail (which is only exponential). Our results contain some constants that must be determined numerically. We use formal asymptotic methods of applied mathematics such as the WKB method and matched asymptotics. Keywords: Algorithms, Analysis of algorithms, Asymptotic analysis, Binary search tree, Quicksort, Sorting. 1 Introduction
Pattern Matching Image Compression Algorithmic and Empirical Results.
 
Entropy Computations via Analytic Depoissonization.
We investigate the basic question of information theory, namely, evaluation of Shannon entropy, and a more general Rényi entropy, for some discrete distributions (e.g., binomial, negative binomial, etc.). We aim at establishing analytic methods (i.e., those in which complex analysis plays a pivotal role) for such computations which often yield estimates of unparalleled precision. The main analytic tool used here is that of analytic poissonization and depoissonization. We illustrate our approach on the entropy evaluation of the binomial distribution, that is, we prove that for Binomial(n; p) distribution the entropy h n becomes h n i 1 2 ln n+ 1 2 +ln p 2ßp(1 \Gamma p)+ P k1 a k n \Gammak where a k are explicitly computable constants. Moreover, we shall argue that analytic methods (e.g., complex asymptotics such as Rice&#039;s method and singularity analysis, Mellin transforms, poissonization and depoissonization) can offer new tools for information theory, especially for studying ...
Indexing and mapping of proteins using a modified nonlinear Sammon projection.
A modified Sammon algorithm was developed to display a relationship between proteins based on their amino acid composition. In the first stage of the method, a 19-dimensional compositional space of representative proteins was mapped into a 2-dimensional space (2-D) using the original Sammon projection creating a contour map. In the second stage, this contour map was used as a reference for new proteins projected into 2-D. Data analysis showed that proteins belonging to the same structural classes formed characteristic and distinct clusters, which could be potentially useful in the prediction of protein structural classes. However, we observed significant overlapping of the clusters which may explain the limited success of previous protein folding prediction based solely on amino acid composition. Regardless, the modified Sammon projections can generate a unique index for each individually projected protein related to its amino acid composition, which may be a useful tool in the exploratory classification of proteins.
Average Profile of the Generalized Digital Search Tree and the Generalized Lempel%2DZiv Algorithm.
The goal of this research is threefold: (i) to analyze generalized digital search trees, (ii) to derive the average profile (i.e., phrase length) of a generalization of the well known parsing algorithm due to Lempel and Ziv, and (iii) to provide analytical tools to analyze asymptotically certain partial differential functional equations often arising in the analysis of digital trees. In the generalized Lempel-Ziv parsing scheme, one partitions a sequence of symbols from a finite alphabet into phrases such that the new phrase is the shortest substring seen in the past by at most b \Gamma 1 phrases (b = 1 corresponds to the original Lempel--Ziv scheme). Such a scheme can be analyzed through a generalized digital search tree in which every node is capable of storing up to b strings. In this paper, we investigate the depth of a randomly selected node in such a tree and the length of a randomly selected phrase in the generalized Lempel-Ziv scheme. These findings and some recent results al...
Complexity of Sequential Pattern Matching Algorithms.
We formally define a class of sequential pattern matching algorithms that includes all variations of Morris-Pratt algorithm. For the last twenty years it was known that the complexity of such algorithms is bounded by a linear function of the text length. Recently, substantial progress has been made in identifying lower bounds. We now prove there exists asymptotically a linearity constant for the worst and the average cases. We use Subadditive Ergodic Theorem and prove an almost sure convergence. Our results hold for any given pattern and text and for stationary ergodic pattern and text. In the course of the proof, we establish some structural property, namely, the existence of &#034;unavoidable positions&#034; where the algorithm must stop to compare. This property seems to be uniquely reserved for Morris-Pratt type algorithms since we observe that a popular pattern matching algorithm proposed by Boyer and Moore does not possess this property. Keywords: String searching, pattern matching, analys...
Quicksort Again Revisited.

Greedy Algorithms for the Shortest Common Superstring That Are Asymptotically Optimal.
There has recently been a resurgence of interest in the shortest common superstring problem due to its important applications in molecular biology (e.g., recombination of DNA) and data compression. The problem is NP-hard, but it has been known for some time that greedy algorithms work well for this problem. More precisely, it was proved in a recent sequence of papers that in the worst case a greedy algorithm produces a superstring that is at most fi times (2  fi  4) worse than optimal. We analyze the problem in a probabilistic framework, and consider the optimal total overlap O  opt  n and the overlap O  gr  n produced by various greedy algorithms. These turn out to be asymptotically equivalent. We show that with high probability lim n!1  O  opt  n  n log n  = lim n!1  O  gr  n  n log n  =  1  H  where n is the number of original strings, and H is the entropy of the underlying alphabet. Our results hold under a condition that the lengths of all strings are not too short.  
Philippe Flajolet%27s Research in Analysis of Algorithms and Combinatorics.

On Pattern Frequency Occurrences in a Markovian Sequence.
Consider a given pattern H and a random text T generated by a Markovian source. We study the frequency of pattern occurrences in a random text when overlapping copies of the pattern are counted separately. We present exact and asymptotic formulae for all moments (including the variance), and probability of r pattern occurrences for three different regions of r, namely: (i) r = O(1), (ii) central limit regime, and (iii) large deviations regime. In order to derive these results, we first construct some language expressions that characterize pattern occurrences which are later translated into generating functions. Finally, we use analytical methods to extract asymptotic behaviors of the pattern frequency. Applications of these results include molecular biology, source coding, synchronization, wireless communications, approximate pattern matching, game theory, and stock market analysis. These findings are of particular interest to information theory (e.g., second-order properties of the re...
Analytical Depoissonization and its Applications.

Stability analysis of quota allocation access protocols in ring networks with spatial reuse.
We consider a slotted ring that allows simultaneous transmissions of messages by different nodes, known as ring with spatial reuse. To alleviate fairness problems that arise in such networks, policies have been proposed that operate in cycles and guarantee that a certain number of packets, not exceeding a given number called a quota, will be transmitted by every node in every cycle. In this paper, we provide sufficient and necessary stability conditions that implicitly characterize the stability region for such rings. These conditions are derived by extending a technique developed for some networks of queues satisfying a monotonicity property. Our approach to instability is novel and its peculiar property is that it is derived from the instability of a dominant system. Interestingly, the stability region depends on the entire distribution of the message arrival process and the steady-state average cycle lengths or lower dimensional systems, leading to a region with nonlinear boundaries, the exact computation of which is in general intractable. Next, we introduce the notions of essential and absolute stability region. An arrival rate vector belongs to the former region if the system is stable under any arrival distribution with this arrival vector, while it belongs to the latter if there exists some distribution with this rate vector for which the system is stable. Using a linear programming approach, we derive bounds for these stability regions that depend only on conditional average cycle lengths. For the case of two nodes, we provide closed-form expressions for the essential stability region.
Analysis of an Asymmetric Leader Election Algorithm.
We consider a leader election algorithm in which a set of distributed objects  (people, computers, etc.) try to identify one object as their leader. The  election process is randomized, that is, at every stage of the algorithm those  objects that survived so far flip a biased coin, and those who received, say a  tail, survive for the next round. The process continues until only one objects  remains. Our interest is in evaluating the limiting distribution and the first  two moments of the number of rounds needed to select a leader. We establish  precise asymptotics for the first two moments, and show that the asymptotic  expression for the duration of the algorithm exhibits some periodic fluctuations  and consequently no limiting distribution exists. These results are proved by  analytical techniques of the precise analysis of algorithms such as: analytical  poissonization and depoissonization, Mellin transform, and complex analysis.
On the average redundancy rate of the Lempel%2DZiv code.
In this paper, we settle a long standing open problem concerning the average redundancy,  r n , of the Lempel-Ziv&#039;78 (LZ78) code. We prove that for a memoryless source the average redundancy rate attains asymptotically Er n = (A + ffi(n))= log n + O(log log n= log  2  n),  where A is an explicitly given constant that depends on source characteristics, and ffi(x)  is a fluctuating function with a small amplitude. We also derive the leading term for the  kth moment of the number of phrases. We conclude by conjecturing a precise formula on the expected redundancy for a Markovian source. The main result of this paper is a consequence of recently obtained second-order properties of the Lempel-Ziv algorithm [P. Jacquet, W. Szpankowski, Theoretical Computer Science, 144, 1995]. These findings have been established by analytical techniques of the precise analysis of algorithms. We give a brief survey of these results since they are interesting in their own right, and shed some light on the pro...
Stability analysis of quota allocation access protocols in ring networks with spatial reuse.
We consider a slotted ring that allows simultaneous transmissions of messages by different nodes, known as ring with spatial reuse. To alleviate fairness problems that arise in such networks, policies have been proposed that operate in cycles and guarantee that a certain number of packets, not exceeding a given number called a quota, will be transmitted by every node in every cycle. In this paper, we provide sufficient and necessary stability conditions that implicitly characterize the stability region for such rings. These conditions are derived by extending a technique developed for some networks of queues satisfying a monotonicity property. Our approach to instability is novel and its peculiar property is that it is derived from the instability of a dominant system. Interestingly, the stability region depends on the entire distribution of the message arrival process and the steady-state average cycle lengths or lower dimensional systems, leading to a region with nonlinear boundaries, the exact computation of which is in general intractable. Next, we introduce the notions of essential and absolute stability region. An arrival rate vector belongs to the former region if the system is stable under any arrival distribution with this arrival vector, while it belongs to the latter if there exists some distribution with this rate vector for which the system is stable. Using a linear programming approach, we derive bounds for these stability regions that depend only on conditional average cycle lengths. For the case of two nodes, we provide closed-form expressions for the essential stability region.
A suboptimal lossy data compression based on approximate pattern matching.
A practical suboptimal (variable source coding) algorithm for lossy data compression is presented. This scheme is based on approximate string matching, and it naturally extends the lossless Lempel-Ziv data compression scheme. Among others we consider the typical length of approximately repeated pattern within the first n positions of a stationary mixing sequence where D% of mismatches is allowed. We prove that there exists a constant r 0 (D) such that the length of such an approximately repeated pattern converges in probability to 1=r 0 (D) log n (pr.) but it almost surely oscillates between 1=r \Gamma1 (D) log n and 2=r 1 (D) log n,  where r \Gamma1 (D) ? r 0 (D) ? r 1 (D)=2 are some constants. These constants are natural generalizations of R&#039;enyi entropies to the lossy environment. More importantly, we show that the compression ratio of a lossy data compression scheme based on such an approximate pattern matching is asymptotically equal to r 0 (D). We also establish the asymptotic be...
Correction to %27A Suboptimal Lossy Data Compression Based on Approximate Pattern Matching%27.

Analysis of algorithms.
Despite many empirical successes of spectral clustering methods -- algorithms that cluster points using eigenvectors of matrices derived  from the distances between the points -- there are several unresolved  issues. First, there is a wide variety of algorithms that  use the eigenvectors in slightly different ways. Second, many of  these algorithms have no proof that they will actually compute a  reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected  to do well. We also show surprisingly good experimental results on  a number of challenging clustering problems.  
Pattern Matching Image Compression.
 
On the Average Redundancy Rate of the Lempel%2DZiv Code.
In this paper, we settle a long standing open problem concerning the average redundancy,  r n , of the Lempel-Ziv&#039;78 (LZ78) code. We prove that for a memoryless source the average redundancy rate attains asymptotically Er n = (A + ffi(n))= log n + O(log log n= log  2  n),  where A is an explicitly given constant that depends on source characteristics, and ffi(x)  is a fluctuating function with a small amplitude. We also derive the leading term for the  kth moment of the number of phrases. We conclude by conjecturing a precise formula on the expected redundancy for a Markovian source. The main result of this paper is a consequence of recently obtained second-order properties of the Lempel-Ziv algorithm [P. Jacquet, W. Szpankowski, Theoretical Computer Science, 144, 1995]. These findings have been established by analytical techniques of the precise analysis of algorithms. We give a brief survey of these results since they are interesting in their own right, and shed some light on the pro...
Analysis of a splitting process arising in probabilistic counting and other related algorithms.
We present an analytical method of analyzing a class of &#034;splitting algorithms&#034; that include probabilistic counting, selecting the leader, estimating the number of questions necessary to identify distinct objects, searching algorithms based on digital tries, approximate counting, and so forth. In our discussion we concentrate on the analysis of a generalized probabilistic counting algorithm. Our technique belongs to the toolkit of the analytical analysis of algorithms, and it involves solutions of functional equations, analytical poissonization and depoissonization as well as Mellin transform. In particular, we deal with an instance of the functional equation g(z) = fia(z)g(z=2) + b(z) where a(z) and b(z) are given functions, and fi ! 1 is a constant. With respect to our generalized probabilistic counting algorithm, we obtain asymptotic expansions of the first two moments of an estimate of the cardinality of a set that is computed by the algorithm. We also derive the asymptotic distrib...
Greedy Algorithms for the Shortest Common Superstring that are Asmtotically Optimal.

On Pattern Occurrences in a Random Text.
Consider a given pattern H and a random text T of length n. We assume that symbols in the text occur independently, and various symbols have different probabilities of occurrence (i.e., the so called asymmetric Bernoulli model). We are concerned with the probability of exactly r occurrences of H in the text T. We derive the generating function of this probability, and show that asymptotically it behaves as ffn  r  ae  n\Gammar\Gamma1  H , where ff is an explicitly computed constant, and ae H ! 1 is the root of an equation depending on the structure of the pattern. We then extend these findings to random patterns. Key Words: Pattern occurrence, Bernoulli model, autocorrelation polynomial, generating functions, asymptotic analysis.   Research of this author was supported by NSF Grants CCR-9201078 and NCR-9206315, and NATO Collaborative Grant CGR.950060.  1. INTRODUCTION  Repeated patterns and related phenomena in words (sequences, strings) are known to play a central role in many facets...
Analysis of a splitting process arising in probabilistic counting and other related algorithms.
We present an analytical method of analyzing a class of &#034;splitting algorithms&#034; that include probabilistic counting, selecting the leader, estimating the number of questions necessary to identify distinct objects, searching algorithms based on digital tries, approximate counting, and so forth. In our discussion we concentrate on the analysis of a generalized probabilistic counting algorithm. Our technique belongs to the toolkit of the analytical analysis of algorithms, and it involves solutions of functional equations, analytical poissonization and depoissonization as well as Mellin transform. In particular, we deal with an instance of the functional equation g(z) = fia(z)g(z=2) + b(z) where a(z) and b(z) are given functions, and fi ! 1 is a constant. With respect to our generalized probabilistic counting algorithm, we obtain asymptotic expansions of the first two moments of an estimate of the cardinality of a set that is computed by the algorithm. We also derive the asymptotic distrib...
Generalized Lempel%2DZiv Parsing Scheme and its Preliminary Analysis of the Average Profile.

A probabilistic Analysis of a String Editing Problem and its Variations.
We consider a string editing problem in a probabilistic framework. This problem is of considerable interest to many facets of science, most notably molecular biology and computer science. A string editing transforms one string into another by performing a series of weighted edit operations of overall maximum (minimum) cost. The problem is equivalent to finding an optimal path in a weighted grid graph. In this paper, we provide several results regarding a typical behavior of such a path. In particular, we observe that the optimal path (i.e., edit distance) is almost surely (a.s.) equal to ffn for large n where ff  is a constant and n is the sum of lengths of both strings. More importantly, we show that the edit distance is well concentrated around its average value. In the so called independent model in which all weights (in the associated grid graph) are statistically independent, we derive some bounds for the constant ff. As a by-product of our results, we also present a precise estim...
Average profile and limiting distribution for a phrase size in the Lempel%2DZiv parsing algorithm.
Consider the parsing algorithm due to Lempel and Ziv that partitions a sequence of length n into variable phrases (blocks) such that a new block is the shortest substring not seen in the past as a phrase. In practice the following parameters are of interest: number of phrases, the size of a phrase, the number of phrases of given size, and so forth. In this paper, we focus on the size of a randomly selected phrase, and the average number of phrases of a given size (the so called average profile of phrase sizes). These parameters can be efficiently analyzed through a digital search tree representation. For a memoryless source with unequal  probabilities of symbols generation (the so called asymmetric Bernoulli model), we prove that the size of a typical phrase is asymptotically normally distributed with mean and the variance explicitly computed. In terms of digital search trees, we prove the normal limiting distribution of the typical depth (i.e., the length of a path from the root to a ...
A Lossy Data Compression Based on String Matching Preliminary Analysis and Suboptimal Algorithms.
. A practical suboptimal algorithm (source coding) for lossy (non-faithful) data compression is discussed. This scheme is based on an approximate string matching, and it naturally extends lossless (faithful) Lempel-Ziv data compression scheme. The construction of the algorithm is based on a careful probabilistic analysis of an approximate string matching problem that is of its own interest. This extends Wyner-Ziv model to lossy environment. In this conference version, we consider only Bernoulli model (i.e., memoryless channel) but our results hold under much weaker probabilistic assumptions. 1 Introduction  Repeated patterns and related phenomena in words (sequences, strings) play a central role in many facets of telecommunications and theoretical computer science, notably in coding theory and data compression, in the theory of formal languages, and in the design and analysis of algorithms. For example: in faithful data compressions, such a repeated subsequence can be used to reduce th...
On asymptotics of certain sums arising in coding theory.
Recently, T. Kløve [IEEE IT, 41, 1995] analyzed the average worst case probability of undetected error for linear [n; k; q] codes of length n and dimension k over an alphabet of size q. The following sum S n =  P n i=1  \Gamma n i  \Delta  (i=n)  i  (1 \Gamma i=n)  n\Gammai  arose, which has also some other applications in coding theory, average case analysis of algorithms, and combinatorics. T. Kløve conjectured an asymptotic expansion of this sum, and we prove its enhenced version in this note. Furthermore, we consider a more challenging sum arising in the upper bound of the average worst case probability of undetected error over systematic codes derived by Massey. Namely: S n;k =  P n i=1  \Gamma n\Gammak i  \Delta  (i=n)  i  (1 \Gamma i=n)  n\Gammai  for k  0. We obtain an asymptotic expansion of S n;k , and this leads to a conclusion that Massey&#039;s bound on the average worst case probability over all systematic codes is better for every k than the corresponding Kløve&#039;s bound over a...
A scheduling policy with maximal stability region for ring networks with spatial reuse.
A slotted ring that allows simultaneous transmissions of messages by different users is considered. Such a ring network is commonly called ring with spatial reuse. It can achieve significantly higher throughput than standard token rings but it also raises the issue of fairness since some nodes may be prevented from accessing the ring for long time intervals. Policies that operate in cycles and guarantee that a certain number (quota) of packets will be transmitted by every node in every cycle have been considered before to deal with the fairness issue. In this paper we address the problem of designing a policy that results in a stable system whenever the end-to-end arrival rates are within the stability region of the ring with spatial reuse (the stability region of the ring is defined as the set of end-to-end arrival rates for which there is a policy that makes the ring stable). We provide such a policy, which does not require knowledge of end-to-end arrival rates. The policy is an adap...
Asymptotic Behavior of the Lempel%2DZiv Parsing Scheme and Digital Search Trees.
The Lempel-Ziv parsing scheme finds a wide range of applications, most notably in data compression and algorithms on words. It partitions a sequence of length n into variable phrases such that a new phrase is the shortest substring not seen in the past as a phrase. The parameter of interest is the number M n of phrases that one can construct from a sequence of length n. In this paper, for the memoryless source with unequal probabilities of symbols generation we derive the limiting distribution of M n which turns out to be normal. This proves a long standing open problem. In fact, to obtain this result we solved another open problem, namely, that of establishing the limiting distribution of the internal path length in a digital search tree. The latter is a consequence of an asymptotic solution of a multiplicative differential-functional equation often arising in the analysis of algorithms on words. Interestingly enough, our findings are proved by a combination of probabilistic techniques such as renewal equation and uniform integrability, and analytical techniques such as Mellin transform, differential-functional equations, de-Poissonization, and so forth. In concluding remarks we indicate a possibility of extending our results to Markovian models.
A Lossy Data Compression Based on String Matching Preliminary Analysis and Suboptimal Algorithms.
. A practical suboptimal algorithm (source coding) for lossy (non-faithful) data compression is discussed. This scheme is based on an approximate string matching, and it naturally extends lossless (faithful) Lempel-Ziv data compression scheme. The construction of the algorithm is based on a careful probabilistic analysis of an approximate string matching problem that is of its own interest. This extends Wyner-Ziv model to lossy environment. In this conference version, we consider only Bernoulli model (i.e., memoryless channel) but our results hold under much weaker probabilistic assumptions. 1 Introduction  Repeated patterns and related phenomena in words (sequences, strings) play a central role in many facets of telecommunications and theoretical computer science, notably in coding theory and data compression, in the theory of formal languages, and in the design and analysis of algorithms. For example: in faithful data compressions, such a repeated subsequence can be used to reduce th...
A functional equation often arising in the analysis of algorithms %28extended abstract%29.

Autocorrelation on Words and Its Applications %2D Analysis of Suffix Trees by String%2DRuler Approach.
We study in a probabilistic framework some topics concerning the way words can overlap. Our probabilistic models assumes that a word is a sequence of i.i.d. symbols generated from a finite alphabet. This defines the so called Bernoulli model. We investigate the length of a subword that can be recopied, that is, a subword that occurs at least twice in a given word. An occurrence of such repeated substrings is easy to detect in a digital tree called a suffix tree. The length of a repeated substring corresponds to the typical depth in the associated suffix tree. Our main finding shows that the typical depth in a suffix tree is asymptotically distributed in the same manner as the typical depth in a digital tree that stores independent keys (i.e., independent tries). More precisely, we prove that the typical depth in a suffix tree built from the first n suffixes of a random word is normally distributed with the mean asymptotically becoming 1=h 1 log n and the variance ff \Delta log n, where...
Digital Search Trees Again Revisited The Internal Path Length Perspective.

Analysis of a String Edit Problem in a Probabilistic Framework %28Extended Abstract%29.

Asymptotic properties of data compression and suffix trees.
Recently, Wyner and Ziv have proved that the typical length of a repeated subword found within the first n positions of a stationary ergodic sequence is (1=h) log n in probability where h is the entropy of the alphabet. This finding was used to obtain several insights into certain universal data compression schemes, most notably the Lempel-Ziv data compression algorithm. Wyner and Ziv have also conjectured that their result can be extended to a stronger almost sure convergence. In this paper, we settle this conjecture in the negative in the so called right domain asymptotic, that is, during a dynamic phase of expanding the data base. We prove -- under an additional assumption involving mixing conditions -- that the length of a typical repeated subword oscillates almost surely (a.s.) between (1=h 1 ) log n and (1=h 2 ) log n where 0 ! h 2 ! h h 1 ! 1. We also show that the length of the nth block in the Lempel-Ziv parsing algorithm reveals a similar behavior. We relate our findings to...
A Note on Binomial Recurrences Arising in the Analysis of Algorithms.

Multidimensional Digital Searching and Some New Parameters in Tries.
Multidimensional digital searching (M-d tries) is analyzed from the view point of partial match retrieval. Our first result extends the analysis of Flajolet and Puech of the average cost of retrieval under the Bernoulli model to biased probabilities of symbols occurrences in a key. The second main finding concerns the variance of the cost of the retrieval in the unbiased case. This variance is of order O(N  1\Gammas=M  ) where N is the number of records stored in a M-d trie, and s is the number of specified components in a query of size M . For M = 2 and s = 1 we present a detailed analysis of the variance, which identifies the constant at  p  N . This analysis, which is the central part of our paper, requires certain series transformation identities which go back to Ramanujan. In the Appendix we provide a Mellin transform approach to these results.  y  This work was supported by Fonds zur Forderung der Wissenschaftlichen Forschung Project P7497TEC   z  Support for this research was pr...
A Probabilistic Analysis of a Pattern Matching Problem.
The study and comparison of strings of symbols from a finite or an infinite alphabet is relevant to various areas of science, notably molecular biology, speech recognition, and computer science. In particular, the problem of finding the minimum &#034;distance&#034; between two strings (in general, two blocks of data) is of great importance. In this paper we investigate the (string) pattern matching problem in a probabilistic framework, namely, it is assumed that both strings form an independent sequences of i.i.d. symbols. Given a text string a of length n and a pattern string b of length m, let M m;n be the maximum number of matches between b and all m-substrings of a. Our main probabilistic result shows that M m;n \Gamma mP = \Theta(  p  2m log n) in probability (pr.) provided m;n !1 such that log n = o(m), where P is the probability of a match between any two symbols of these strings. If the alphabet is symmetric (i.e., all symbols occur with the same probability), a stronger result holds, na...
A Generalized Suffix Tree and its %28Un%29expected Asymptotic Behaviors.
Suffix trees find several applications in computer science and telecommunications, most notably in algorithms on strings, data compressions and codes. Despite this, very little is known about their typical behaviors. In a probabilistic framework, we consider a family of suffix trees -- further called b-suffix trees -- built from the first n suffixes of a random word. In this family a noncompact suffix tree (i.e., such that every edge is labeled by a single symbol) is represented by b = 1, and a compact suffix tree (i.e., without unary nodes) is asymptotically equivalent to b ! 1 as n ! 1. We study several parameters of b-suffix trees, namely: the depth of a given suffix, the depth of insertion, the height and the shortest feasible path. Some new results concerning typical (i.e., almost sure) behaviors of these parameters are established. These findings are used to obtain several insights into certain algorithms on words, molecular biology and universal data compression schemes.  Key Wo...
Limiting Distribution for the Depth in Patricia Tries.

Probabilistic Analysis of Generalized Suffix Trees %28Extended Abstract%29.

Pattern Matching With Mismatches A Probabilistic Analysis and a Randomized Algorithm %28Extended Abstract%29.

How to Count Quickly and Accurately A Unified Analysis of Probabilistic Counting and Other Related Problems.

%28Un%29expected Behavior of Typical Suffix Trees.

Self%2DAlignments in Words and Their Applications.
Some quantities associated with periodicities in words are analyzed within the Bernoulli  probabilistic model. In particular, the following problem is addressed. Assume that a string  X is given, with symbols emitted randomly but independently according to some known distribution of probabilities. Then, for each pair (W , Z) of distinct suffixes of X, the expected length of the longest common prefix of W and Z is sought. The collection of these lengths, that are called here self-alignments, plays a crucial role in several algorithmic problems on words, such as building suffix trees or inverted files, detecting squares and other regularities, computing substring statistics, etc. The asymptotically best algorithms for these problems are quite complex and thus risk to be unpractical. The present analysis of self-alignments and related measures suggests that, in a variety of cases, more straightforward algorithmic solutions may yield comparable or even better performances. Key words and ph...
Stability of token passing rings.
Sufficient stability condition for the standard token passing ring is &#034;known&#034; since the seminal paper of Kuehn in 1979. However, this condition was derived without formal proof, and the proof seems to be of considerable interest to research community. In fact, Watson observed that in the performance evaluation of token passing rings &#034;it is convenient to derive stability conditions ... (without proof)&#034;. Our intention is to fill this gap, and provide a formal proof of the sufficient and necessary stability condition for the token passing ring. In this paper we present the case when the arrival process to each queue is Poisson but service times and switchover times are generally distributed. We consider in depth gated  `-limited (`  1) service discipline for each station. We also indicate that the basic steps of our technique can be used to study the stability of some other multiqueue systems. Keywords and Phrases  Token passing rings, stability, substability, ergodicity, Markov chains, L...
A Note on the Height of Suffix Trees.

Maximum Size of a Dynamic Data Structure Hashing with Lazy Deletion Revisited.
We study the dynamic data structure management technique called Hashing with Lazy Deletion (HwLD). A table managed under HwLD is built via a sequence of insertions and deletions of items. When hashing with lazy deletions, one does not delete items as soon as possible, but keeps more items in the data structure than immediate-deletion strategies would. This deferral allows the use of a simpler deletion algorithm, leading to a lower overhead---in space and time---for the HwLD implementation. It is of interest to know how much extra space is used by HwLD. We investigate the maximum size and the excess space used by HwLD, under general probabilistic assumptions, using the methodology of queueing theory. In particular, we find that for the Poisson arrivals and general life-time distribution of items, the excess space does not exceed the number of buckets in HwLD. As a by-product of our analysis, we also derive the limiting distribution of the maximum queue length in an  M jGj1 queueing syst...
Probabilistic Modeling of Data Structures on Words A Reply to Professor Andersson%27s Letter.

A Typical Behaviour of Some Data Compression Schemes.

Combinatorial Optimization Through Order Statistics.

What Can We Learn about Suffix Trees from Independent Tries%3F

On the Height of Digital Trees and Related Problems.

Analysis of digital tries with Markovian dependency.

A Characterization of Digital Search Trees from the Successful Search Viewpoint.

On the Analysis of the Tail Queue Length and Waiting Time Distributions of a GI%2FG%2Fc Queue.

Patricia Tries Again Revisited
We present the nested Chinese restaurant process (nCRP), a stochastic process which assigns probability distributions to infinitely-deep, infinitely-branching trees. We show how this stochastic process can be used as a prior distribution in a Bayesian nonparametric model of document collections. Specifically, we present an application to information retrieval in which documents are modeled as paths down a random tree, and the preferential attachment dynamics of the nCRP leads to clustering of documents according to sharing of topics at multiple levels of abstraction. Given a corpus of documents, a posterior inference algorithm finds an approximation to a posterior distribution over trees, topics and allocations of words to levels of the tree. We demonstrate this algorithm on collections of scientific abstracts from several journals. This model exemplifies a recent trend in statistical machine learning—the use of Bayesian nonparametric methods to infer distributions on flexible data structures.
Digital Search Trees %2D Further Results on a Fundamental Data Structure.

Digital Data Structures and Order Statistics.

Some remarks on uniformly bounded markov chains multimodality analysis.

The presence of exponentiality in entropy maximized M%2FGI%2F1 queues.

On the variance of the external path length in a symmetric digital trie.

Ultimate Characterizations of the Burst Response of an Interval Searching Algorithm A Study of a Functional Equation.

On the Balance Property of Patricia Tries External Path Length Viewpoint.

Do We Really Need to Balance Patricia Trees%3F %28Extended Abstract%29.

On an Alternative Sum Useful in the Analysis of Some Data Structures.

Closed%2Dnetwork duals of multiqueues with application to token%2Dpassing systems.

The Evaluation of an Alternative Sum With Applications to the Analysis of Some Data Structures.

The Evaluation of an Alternative Sum With Applications to the Analysis of Some Data Structures.

Some Results on V%2Dary Asymmetric Tries.

Two Problems on the Average Complexity of Digital Trees.

Average Complexity of Additive Properties for Multiway Tries A Unified Approach %28Extended Abstract%29.

An Analysis of a Contention Resolution Algorithm Another Approach.

On an Asymptotic Analysis of a Tree%2DType Algorithm for Broadcast Communications.

Performance Evaluation of a Reservation Protocol for Multiaccess Systems.

Packet Switching in Multiple Radio Channels Analysis and Stability of a Random Access System.

